package Algorithm.Sort;

import java.util.Arrays;

public class InsertSort {
    // 插入排序
    // 整个区间分为
    // 1.有序区间
    // 2.无序区间
    // 每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入
    public static void insertSort(int[] arr) {
        // 有序区间（已排序区间）[0,i]
        for (int i = 1; i < arr.length; i++) {
            // 待排序区间[i...n]
            // 待排序区间的第一个元素arr[i]
            // 从待排序区间的第一个元素向前看，找到合适的位置插入
            for (int j = i; j > 0; j--) { // 表示取无序区间的第一个元素与有序区间进行比较
                // 循环已排区间
                // arr[j - 1]已排序区间的最后一个元素
                // 相等也不交换，保证稳定性
                // 此时说明arr[j] > 已排区间的最大值，a[j]已经有序了---直接下次循环
                if (arr[j] >= arr[j - 1]) {
                    break;
                } else { // 冒泡排序（arr[j] < arr[j - 1]）
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }

    }

    public static void main(String[] args) {
        int[] arr = {2,1,5,3,7,8,4,9,6,12,10,15,14};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}
